package leetcode;

import util.NodeQ0427.Node;

/**
 * @Project : algorithm-learning-java
 * @Package : leetcode
 * @Author : Ruoyu Wang
 * @User : Momenta
 * @DateTime : 2024/1/6 17:15
 */
public class Q0427 {
    private boolean check(int[][] grid, int x1, int y1, int x2, int y2) {
        int x = grid[x1][y1];
        for (int i = x1; i <= x2; i++) {
            for (int j = y1; j <= y2; j++) {
                if (grid[i][j] != x) return false;
            }
        }
        return true;
    }

    private Node dfs(int[][] grid, int x1, int y1, int x2, int y2) {
        if (check(grid, x1, y1, x2, y2)) return new Node(grid[x1][y1] == 1, true);
        Node res = new Node(true, false);
        int xmid = x1 + x2 >> 1;
        int ymid = y1 + y2 >> 1;
        res.topLeft = dfs(grid, x1, y1, xmid, ymid);
        res.topRight = dfs(grid, x1, ymid + 1, xmid, y2);
        res.bottomLeft = dfs(grid, xmid + 1, y1, x2, ymid);
        res.bottomRight = dfs(grid, xmid + 1, ymid + 1, x2, y2);
        return res;
    }

    public Node construct(int[][] grid) {
        return dfs(grid, 0, 0, grid.length - 1, grid.length - 1);
    }

    public static void main(String[] args) {
        Q0427 sl = new Q0427();
        int[][] grid = {{1, 1, 0, 0}, {0, 0, 1, 1}, {1, 1, 0, 0}, {0, 0, 1, 1}};
        sl.construct(grid);
    }
}
